//拓扑排序 
//优先我们知道 一个有向无环图一定有着我们呢拓扑关系存在的
//那么我们拓扑关系的寻找方法就是：
queue <------让所有入度为0的点。
while queue 不为空
{
	t<---队头
	枚举t所有的出边f
	让每一个f的入度减1
	如果f的入度为0 ，那么就可以加入队列里面
	然后枚举完成 了以后  我们删除t
}


//最短路------------一大块内容-------------------//
//又分为         单源最短路+ 多源汇最短路
	//单源最短路  还可以分为   所有边权都是正数  +  存在负权边
		//所有边权都是正数  的做法： 朴素dijkstra的算法 O（n^2） + 堆优化的dijstra的算法 o(mlogn）； 
		//有负权边  ：  有bellman-ford o(mn)  +  SPFA 一般O(m)最坏o(mn）;
	//多元汇 ： Floyd算法 O(n^3)



//----------朴素dijkstra的算法-----稠密图：用邻接矩阵存放----------//
dijkstra朴素算法思想：
	1： 用临接矩阵来存储，因为是稠密度的，我们算法复杂度就是O(n^2)
	（我们在进行存便之间的关系的时候，已经排除掉重边的干扰了，存的都是最小值）
	2：  每一次找出我们存活点当中的距离最小值
	3： 利用这个最小值去更新所有点的其它点的最小值
	4： 更新完成之后，这个点的使命已经完成，将其杀死；
	5： 以上的动作重复n-1 次；就可以了
dijkstra推优化的算法思想：
	1： 利用邻接表来进行存储，因为是稀密度的，我们的算法复杂度是o (mlogn)
	2:	我们将上面第二步步骤设置未利用堆区维护我们的最小值
	3： 每次取出来最小值之后，看看这个点是已经被杀死的点，如果是则重新取出来，如果不是就进行第四步
	4： 可以先杀死这个点，也可以跟新完成后再杀死。我们利用这个点，去跟新所有和他相连接的点，如果距离变小了，我们就加入队列里面。
	5： 这儿可以看出和朴素版本的区别就是两点：一个是取值，另外一个就是只更新和自己有关的点，而不是朴素算法所有边都来一遍。
bellman_ford算法：
	1.	这种算法一般用于有次数限制的方法，且可以有负权边。 时间复杂度就是0（mn)
	2： 我们存储的方式变为利用一个结构数组保存我们的信息；
	3： 假设k为我们的更新次数，那么我们以下的步骤就循环k次
	4：	每次遍历一下我们结构数组，每次对dist进行一次松弛操作。
	5： 但是一个1/k中，开始一轮遍历，可能出现了在这次遍历中循环更新以后边，所以我们就利用一个last来存上一次的dist
		在last的基础上进行更新。
spfa算法：
	1： 针对bellman_fork算法，我们其实没有必要访问所有的边，只有已知边长度已经减少了我们才会更新这条边后面的边。
		这就有点bfs的感觉了，利用队列来做。
	2.	首先把1号点加进去，并把这个点杀死，然后开始队列的取出-------存入操作
	3： 首先，取出这个点，并将其复活。知道为啥是这一步吗？对比dij算法，我们有负权边，可以后退，而dij全是正数，没有后退的余地。
	4： 然后遍历取出来的点，如果我们的相连的点减少了。我们呢判断是否在队列里面，如果不再就加入，并将其杀死，以便后面取出来
		跟新其它和它相邻的点。
	5： 所以这儿的st[N]有两种功能，判断否已经在队列里面。（隐藏了一种杀死复活的感觉。）
Floyd算法：
	1： 这个算法没有什么好说的，首先明白注意以下几个点就可以了
	2： 由于多元 dist就应该是二元数组  初始化问题就必须进行手动进行
	3： 其实这就是一个三维的动态规划问题 记住公式：d[i][j]=min(d[i][j],d[i][k]+d[k][j]);ijk都是从1先开始循环到m;m为点数；


int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
		//在st==false的点当中找到 dist最小的点  //遍历了n次找到我们的点  //如果用堆来做 那么就是o(1)
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离  ---遍历了m次边        //如果用堆来做，那么就是修改m次,每次longn；
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
		//做完以上过程  那么这个t就已经可以确定了
        st[t] = true;
    }
	//如果最后n的最短距离还是无穷大 那么我们就是没有最短距离 
    if (dist[n] == 0x3f3f3f3f) return -1;   因为这儿没有负权路，所用dist[n] 不可能只是稍微减少一点点；
    return dist[n];
}
//------------------------end------------------------------------//


//-----------------------dijkstra堆优化版本--------------------------//
  可以手写堆                 也可以使用优先队列 
 可以修改我们的值            不能够修改我们的值
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
//----------------------------end---------------------------------//

//-----------------------------bellman-ford算法----------------------------------//
可以用来求负环  但一般不用这种算法
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}
//-------------------------------end-------------------------------//

 











